<?php
// F(0)=0，F(1)=1, F(n)=F(n - 1)+F(n - 2)

 function fibRec($num) {
    if($num <= 1) {
        return $num;
    }
    return fibRec($num - 1) + fibRec($num - 2);
}

function fib($num) {
    if($num <= 1) {
        return $num;
    }

    $dp = array(
        0 => 0,
        1 => 1
    );

    for ($i=2; $i<=$num; $i++) {
        $dp[$i] = ($dp[$i-1] + $dp[$i-2])%1000000007;
    }

    return $dp[$num];
}

class Solution {

    /**
     * @param Integer $n
     * @return Integer
     */
    private $map=[];//备忘录
    function fib($n) {
        if(isset($this->map[$n])){//先搜索备忘录
            return $this->map[$n];
        }
        if($n<=1){
            $this->map[$n]=$n;
            return $n;
        }

        $this->map[$n]=$this->fib($n-1)+$this->fib($n-2);//设置备忘录
        return $this->map[$n]%1000000007;//取模后返回结果
    }
}